/**
 * 37. 解数独
 * 
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图T37-1、T37-2）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * 
 * 输入：board = 
 * [["5","3",".",".","7",".",".",".","."],
 *  ["6",".",".","1","9","5",".",".","."],
 *  [".","9","8",".",".",".",".","6","."],
 *  ["8",".",".",".","6",".",".",".","3"],
 *  ["4",".",".","8",".","3",".",".","1"],
 *  ["7",".",".",".","2",".",".",".","6"],
 *  [".","6",".",".",".",".","2","8","."],
 *  [".",".",".","4","1","9",".",".","5"],
 *  [".",".",".",".","8",".",".","7","9"]]
 * 
 * 输出：
 * [["5","3","4","6","7","8","9","1","2"],
 *  ["6","7","2","1","9","5","3","4","8"],
 *  ["1","9","8","3","4","2","5","6","7"],
 *  ["8","5","9","7","6","1","4","2","3"],
 *  ["4","2","6","8","5","3","7","9","1"],
 *  ["7","1","3","9","2","4","8","5","6"],
 *  ["9","6","1","5","3","7","2","8","4"],
 *  ["2","8","7","4","1","9","6","3","5"],
 *  ["3","4","5","2","8","6","1","7","9"]]
 *  解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 *  
 *  提示：
 *  board.length == 9
 *  board[i].length == 9
 *  board[i][j] 是一位数字或者 '.'
 *  题目数据 保证 输入数独仅有一个解
 *  
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/sudoku-solver
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

package zw;

class T37 {
	public static void solveSudoku(char[][] board) {
		// 记录某行，某位数字是否被摆放
		boolean[][] row = new boolean[9][9];
		// 记录某列，某位数字是否被摆放
		boolean[][] column = new boolean[9][9];
		// 记录九宫格某位数字是否被摆放
		boolean[][] block = new boolean[9][9];

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.') {
					int num = board[i][j] - '1';
					row[i][num] = column[j][num] = block[i / 3 * 3 + j / 3][num] = true;
				}
			}
		}

		dfs(board, row, column, block, 0);
	}

	private static boolean dfs(char[][] board, boolean[][] row, boolean[][] column, boolean[][] block, int index) {
		int r = index / 9; // 所在行
		int c = index % 9; // 所在列
		int b = r / 3 * 3 + c / 3; // 所在块

		if (board[r][c] != '.' && index == 80 ) {
			return true;
		}

		if (board[r][c] != '.') { // 该位原本就存在数字，进入到下一位
			return dfs(board, row, column, block, index + 1);
		} else {
			for (int i = 0; i < 9; i++) {
				if (!row[r][i] && !column[c][i] && !block[b][i]) {
					row[r][i] = column[c][i] = block[b][i] = true;
					board[r][c] = (char) ('1' + i);
					if (dfs(board, row, column, block, index)) {
						return true;
					} else {
						board[r][c] = '.';
						row[r][i] = column[c][i] = block[b][i] = false;
					}
				}
			}
			return false;
		}
	}

	private static void printBoard(char[][] board) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		char[][] board = new char[][] {
			{'.','.','9','7','4','8','.','.','.'},
			{'7','.','.','.','.','.','.','.','.'},
			{'.','2','.','1','.','9','.','.','.'},
			{'.','.','7','.','.','.','2','4','.'},
			{'.','6','4','.','1','.','5','9','.'},
			{'.','9','8','.','.','.','3','.','.'},
			{'.','.','.','8','.','3','.','2','.'},
			{'.','.','.','.','.','.','.','.','6'},
			{'.','.','.','2','7','5','9','.','.'}};
		solveSudoku(board);
		printBoard(board);
	}
}
